#include <stdio.h>

//插入排序
//升序
void insertionSort(int arr[], int n) {
    int i, j;
    int key;  // 存储当前待插入的元素

    // 从第2个元素开始（i=1），默认第1个元素（i=0）已排序
    for (i = 1; i < n; i++) {
        key = arr[i];  // 取出当前待插入的元素
        j = i - 1;     // j指向已排序序列的最后一个元素

        // 1. 从后往前遍历已排序序列
        // 2. 若已排序元素>key，将其向后移动1位（腾出插入位置）
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];  // 元素后移
            j--;                  // 继续向前比较
        }

        // 找到合适位置（j+1），插入key
        arr[j + 1] = key;
    }
}

//冒泡排序
void bubblesort(int*a,int n)
{
    //降序
    int i=0;
    for(int i=0;i<n-1;i++)
    {
        for(int j=0;j<n-1-i;i++)
        {
            if(a[j+1]>a[j])
            {
                swap(&a[j],&a[j+1]);
            }
        }
    }
}

//堆排序
//向上/向下建堆即可
void heapsort(int *a,int n)
{
    heap hp;
    heapinitdown(&hp,a,n);
    int i=0;
    while(!heapempty(&hp))
    {
        a[i++]=heaptop(&hp);
        heappop(&hp);
    }
    heapdestory(&hp);
}

//希尔排序/分组插入排序
void shellSort(int arr[], int n) {
    // 1. 初始化增量gap（从n/2开始，每次减半，直到gap=0结束）
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 2. 对每个"分组"执行插入排序（i从gap开始，对应每组的第2个元素）
        for (int i = gap; i < n; i++) {
            int key = arr[i];  // 暂存当前待插入的元素（分组中的待插入项）
            int j;

            // 3. 组内从后往前比较，移动元素（步长为gap，而非1）
            // j >= 0 保证不越界，arr[j] > key 时需要移动元素
            for (j = i; j >= gap && arr[j - gap] > key; j -= gap) {
                arr[j] = arr[j - gap];  // 元素按gap步长后移
            }
            // 4. 找到合适位置，插入key
            arr[j] = key;
        }
    }
}

//直接选择排序
//遍历整个数组找到最小值并和第一个元素交换，依次到数组最后

void selectSortAsc(int arr[], int n) {
    int i, j;
    // 外层循环：控制有序区的末尾（i是无序区的第一个元素索引）
    for (i = 0; i < n - 1; i++) {
        int minIndex = i;  // 假设无序区第一个元素是最小值，记录其索引
        
        // 内层循环：遍历无序区（i~n-1），找到最小值的索引
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {  // 找到更小的元素，更新minIndex
                minIndex = j;
            }
        }
        
        // 优化：如果最小值就是无序区第一个元素，无需交换
        if (minIndex != i) {
            // 交换“无序区第一个元素”和“最小值元素”
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

//快排

void QuickSort(int array[], int low, int high) {
    int i = low; 
    int j = high;
    if(i >= j) {
        return;
    }
 
    int temp = array[low];
    while(i != j) {
        while(array[j] >= temp && i < j) {
            j--;
        }
	while(array[i] <= temp && i < j) {
            i++;
        }
	if(i < j) {
            swap(array[i], array[j]);
        }
    }
 
    //将基准temp放于自己的位置，（第i个位置）
    swap(array[low], array[i]);
    QuickSort(array, low, i - 1);
    QuickSort(array, i + 1, high);
}

//归并排序

void merge(int arr[], int low, int mid, int high, int temp[]) {
    int i = low;      // 左子数组的指针（起始于low）
    int j = mid + 1;  // 右子数组的指针（起始于mid+1）
    int k = 0;        // 临时数组的指针（起始于0）

    // 1. 同时遍历两个有序子数组，按升序存入临时数组
    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) {  // 左子数组元素更小，存入临时数组
            temp[k++] = arr[i++];
        } else {  // 右子数组元素更小，存入临时数组
            temp[k++] = arr[j++];
        }
    }

    // 2. 将左子数组剩余元素（若有）全部存入临时数组
    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    // 3. 将右子数组剩余元素（若有）全部存入临时数组
    while (j <= high) {
        temp[k++] = arr[j++];
    }

    // 4. 将临时数组的有序元素拷贝回原数组的对应区间[low, high]
    k = 0;  // 重置临时数组指针
    while (low <= high) {
        arr[low++] = temp[k++];
    }
}

/**
 * 归并排序递归函数：拆分+合并
 * 参数：
 *   arr - 待排序数组
 *   low - 当前区间左边界
 *   high - 当前区间右边界
 *   temp - 临时数组（提前分配，避免递归中重复分配释放，提升效率）
 */
void mergeSort(int arr[], int low, int high, int temp[]) {
    // 递归终止条件：子数组长度<=1（无需拆分，天然有序）
    if (low < high) {
        int mid = low + (high - low) / 2;  // 中间拆分点（避免low+high溢出）
        
        // 1. 递归拆分左子数组 [low, mid]
        mergeSort(arr, low, mid, temp);
        // 2. 递归拆分右子数组 [mid+1, high]
        mergeSort(arr, mid + 1, high, temp);
        // 3. 合并两个有序子数组
        merge(arr, low, mid, high, temp);
    }
}

/**
 * 对外接口函数：简化调用（无需用户手动分配临时数组）
 * 参数：arr - 待排序数组，n - 数组长度
 */
void mergeSortAsc(int arr[], int n) {
    if (n <= 1) return;  // 数组长度<=1，直接返回
    // 分配临时数组（大小为n，仅分配一次，提升效率）
    int* temp = (int*)malloc(n * sizeof(int));
    if (temp == NULL) {  // 内存分配失败处理
        printf("内存分配失败！\n");
        return;
    }
    // 调用递归排序函数
    mergeSort(arr, 0, n - 1, temp);
    // 释放临时数组（避免内存泄漏）
    free(temp);
}

    